/*
7.30
time:20201210 14:16 PM
key:1.巧妙运用了bool函数作为返回值，成功影响上一次递归。
user：ldc
*/

#include <iostream>
using namespace std;
#include<stack>
#include<queue>
class Tree
{
public:
	int data;
	Tree* lchild;
	Tree* rchild;
	bool left_flag = false;   //左指针域类型  false：指向子节点、true：前驱或后继线索
	bool right_flag = false;  //右指针域类型  false：指向子节点、true：前驱或后继线索

	Tree()
	{
		data = -1;
		lchild = NULL;
		rchild = NULL;
	}
};
//逐个元素写入树
void write(Tree* node, int x)
{
	if (node != NULL)
	{
		
		if (node->data == -1 )
		{
			node->data=x;
			node->lchild = new Tree;
			node->rchild = new Tree;
		}
		else
		{
			if (node->data < x )
			{
				if (node->rchild == NULL)
				{
					node->rchild = new Tree;
					node->rchild->data = x;
				}
				else
				{
					write(node->rchild, x);
				}
			}
			if (node->data > x )
			{
				if (node->lchild == NULL)
				{
					node->lchild = new Tree;
					node->lchild->data = x;
				}
				else
				{
					write(node->lchild, x);
				}
			}
		}

	}
}
//先序遍历改造树(空节点改为NULL)
void change(Tree* node)
{
	if (node != NULL)

	{
		if (node->lchild->data == -1)
		{
			node->lchild = NULL;
		}
		if (node->rchild->data == -1)
		{
			node->rchild = NULL;
		}
		change(node->lchild);
		change(node->rchild);

	}
}
//中序遍历输出树()
void PerOrder_read(Tree* node, queue<int>&sort)
{
	if (node != NULL)

	{
		
		PerOrder_read(node->lchild, sort);
		cout << node->data << " ";
		sort.push(node->data);
		PerOrder_read(node->rchild, sort);

	}
}

//删除二叉搜索树的最大节点
bool del_max(Tree* node, Tree* node_right)
{
	if (node->rchild!=NULL)

	{

		if (del_max(node->rchild, node->rchild->rchild))
		{//找到node右孩子这个就是最大元素节点，同时node右孩子的node右孩子一定为空。
			//如果这个最大元素节点左为空，则直接删掉
			if (node->rchild->lchild == NULL )
			{
				cout << "\n二叉树内最大元素左子树为空" << endl;
				node->rchild = NULL;
			}
			//如果这个最大元素节点左节点不为空，则将左子树直接替代最大元素节点即可。
			{
				cout << "\n二叉树内最大元素左子树不为空" << endl;
				node->rchild = node->rchild->lchild;
			}
			
		}
		return 0;
	}
	else
	{
		if (node != NULL)
		{
			cout << node->data;
			return 1;
		}
	}
}



int main()
{
	Tree* head = new Tree;
	queue<int>array;
	queue<int> sort_array;
	int x;
	//二叉树内最大元素左子树为空
	//10 0 1 2 3 4 5 6 7 8 9 
	//二叉树内最大元素左子树不为空
	//10 1 9 2 8 3 7 4 6 5 0
	
	int n, i;
	//输入n个int型
	cin >> n;
	for (i = 0; i < n; i++)
	{
		cin >> x;
		array.push(x);
	}
	while (!array.empty())
	{
		x = array.front();
		array.pop();
		write(head, x);
	}

	cout << "\n" << endl;
	//改造空节点
	change(head);
	//中序遍历并放入数组
	cout << "\n中序遍历并按序放入数组" << endl;
	PerOrder_read(head, sort_array);
	//遍历并删除二叉树内最大元素
	cout << "\n二叉树内最大元素是" << endl;
	del_max(head,head->rchild);
	//再次中序遍历
	cout << "\n删除最大元素后的中序遍历" << endl;
	PerOrder_read(head, sort_array);
}




